'''
Module: ep_core.py
Purpose: Implements the Earley parsing logic.
Author: Avishay Alon
'''
#########################################
### Imports
#########################################
from collections import defaultdict
from ep_grammar import Rule
from copy import deepcopy

#########################################
### Globals
#########################################
__DEBUG__ = False
def debug(chars):
    if __DEBUG__:
        print chars

#########################################
### Classes
#########################################
class DottedRule(object):
    ''' The DottedRule object contains a Rule object and a dot index property. '''
    def __init__(self, rule, dot_index):
        self._rule = rule
        self._dot_index = dot_index
        self._is_active = dot_index < len(rule)

    def next_term(self):
        ''' Return the term/symbol following the dot index. '''
        return self._rule.production.split()[self._dot_index]

    def __str__(self):
        return '%s, dot_index = %d' % (self._rule, self._dot_index, )

    def __eq__(self, other):
        return (self._rule == other.rule and 
                    self._dot_index == other.dot_index)
    def __ne__(self, other):
        return not (self == other)

    production = property(lambda self: self._rule.production)
    active = property(lambda self: self._is_active)
    rule = property(lambda self: self._rule)
    dot_index = property(lambda self: self._dot_index)

class EarleyParser(object):
    ''' This class contains all the logic of the Earley parsing algorithm. 
        Assumes the grammar given is of class Grammar. '''
    def __init__(self, grammar):
        ''' Initialization method. must provide grammar. '''
        self._chart = None
        self._grammar = grammar
        self._pairs = set()
        self._words = None
        self._roots = []
        self._root_idx = 0
        self._dfs_q = []
        
    def _get_all_edges(self):
        ''' Scans the chart and returns all the existing edges. '''
        edges = set()
        for i in self._chart.keys():
            for j in self._chart.keys():
                for edge in self._chart[i][j]:
                    edges.add(edge)
        return edges

    def _get_rightsisters(self, edge):
        ''' Given an active edge A -> x*By, 
            create and return edges for rules B -> *z '''
        if not edge.active or edge.rule.is_terminal:
            return []
        term = edge.next_term()
        if term not in self._grammar.nonterminals:
            return []
        return [ DottedRule(rule, 0) for rule in self._grammar.rule_set if rule.head == term ]

    def _get_leftsisters(self, edge):
        ''' Given an inactive/complete edge B -> z*, 
            return all existing edges A -> x*By '''
        if edge.active:
            return []
        return [ leftsister for leftsister in self._get_all_edges()
                    if leftsister.active and
                    leftsister.next_term() == edge.rule.head ]

    def _enteredge(self, i, edge, j):
        ''' Recursively perform predictions and completions on edges. '''
        if edge in self._chart[i][j]:
            return
        self._chart[i][j].append(edge)
        ## Predict
        if edge.active:
            for rightsister in self._get_rightsisters(edge):
                self._enteredge(j, rightsister, j)
        ## Complete
        else:
            for leftsister in self._get_leftsisters(edge):
                for k in [ index for index in self._chart.keys() 
                            if leftsister in self._chart[index][i] ]:
                    combined = DottedRule(leftsister.rule, leftsister.dot_index + 1)

                    self._pairs.add(Pair(combined.rule, edge.rule, indexes=(i, k, j)))

                    self._enteredge(k, combined, j)

    def _init_chart(self):
        ''' Initialize the chart: chart[i][j] = list of edges. '''
        self._chart = {}
        for index in range(len(self._words) + 1):
            self._chart[index] = defaultdict(list)

    def parse(self, words):
        ''' The parse method returns True if the input given is parsable 
            from the grammar given, and False otherwise. '''
        self._words = words
        self._pairs = set()
        self._init_chart()
        ## Add the start rule
        start_rule = Rule("S'", self._grammar.start_symbol)
        self._enteredge(0, DottedRule(start_rule, 0), 0)
        ## Scan the input words
        for j in range(len(words)):
            for rule in self._grammar.terminal_rules:
                if words[j] == rule.production:
                    self._enteredge(j, DottedRule(rule, 1), j + 1)

        ## Is the final edge found in [0][n]?
        return DottedRule(start_rule, 1) in self._chart[0][len(words)]
        
    def _find_and_add_children(self, current):
        next_generation = set([pair for pair in self._pairs if current.child == pair.father])
        childrens = []
        valid = False

        for candidate in next_generation:
            valid = False
            ## Single rule
            if len(current.child) == 1:
                if (candidate.k, candidate.j) == (current.i, current.j):
                    subtree = [candidate]
                    if subtree not in childrens:
                        valid = True
            ## Rule with 2 nonterminals products
            elif len(current.child) == 2:
                for aux in next_generation:
                    if aux == candidate or candidate.k != aux.k:
                        continue
                    ## candidate is the first rule, aux is the second
                    if (current.i, current.j) == (candidate.i, aux.j) and candidate.j == aux.i:
                        subtree = [candidate, aux]
                        if subtree not in childrens and (current.i, current.j) == (aux.k, aux.j):
                            valid = True

                    ## aux is the first rule, candidate is the second
                    if (current.i, current.j) == (aux.i, candidate.j) and aux.j == candidate.i:
                        subtree = [aux, candidate]
                        if subtree not in childrens and (current.i, current.j) == (candidate.k, candidate.j):
                            valid = True

            else:
                raise ValueError(len(current.child))
            
            if valid:
                childrens.append(subtree)
        if childrens:
            for children in childrens[::-1]:
                self._dfs_q += children[::-1]
        return childrens
        
    def create_parse_trees(self):
        self._dfs_q = [pair for pair in self._pairs if pair.father.head == "S'" and pair.j == len(self._words)]
        if len(self._dfs_q) != 1:
            raise ValueError(self._dfs_q)

        start_pair = self._dfs_q[0]
        self._roots = [Node(start_pair.get_father_rule_interval(), [Node(start_pair.get_child_rule_interval(), [])]), ]
        self._root_idx = 0
        leaf_count = None

        while not self._forest_creation_finished():
            if leaf_count is None:
                debug('=== Starting Parse Tree %d/%d===' % (self._root_idx, len(self._roots), ))
                leaf_count = 0

            current = self._dfs_q.pop()
            if current.is_leaf:
                leaf_count += 1
            current_children = self._find_and_add_children(current)

            ### If not a leaf, continue generating the tree
            if not current.is_leaf:
                self._generate_tree(current_children, current)

            self._debug_phase(current, current_children)
            debug('* Root id: %d, leafs: %d' % (self._root_idx, self._roots[self._root_idx].count_leafs(), ))
            if self._roots[self._root_idx].count_leafs() >= len(self._words):
                debug('=== Finished Parse Tree ===')
                self._root_idx += 1
                leaf_count = None

        return self._roots

    def _generate_tree(self, current_children, current):
        if len(current_children) > 1:
            self._add_new_trees(current_children, current)

        latest_node = self._roots[self._root_idx].get(current.get_child_rule_interval())
        new_childs = current_children[0]
        latest_node.children += [Node(child.get_child_rule_interval(), []) for child in new_childs]

    def _add_new_trees(self, current_children, current):
        for children_for_new_tree in current_children[1:][::-1]:
            new_root = deepcopy(self._roots[self._root_idx])
            self._roots.insert(self._root_idx + 1, new_root)
            latest_node = new_root.get(current.get_child_rule_interval())
            latest_node.children = [Node(child.get_child_rule_interval(), []) for child in children_for_new_tree]

    def _forest_creation_finished(self):
        if self._root_idx == len(self._roots):
            for element in self._dfs_q:
                if not element.is_leaf:
                    raise ValueError()
            return True
        else:
            return False

    def _debug_phase(self, current, current_children):
        if not __DEBUG__:
            return

        print '* Cur:', current
        if len(current_children):
            if len(current_children) > 1:
                print '* > New Trees: %d' % (len(current_children) - 1, )
            for index, child in enumerate(current_children):
                if index != 0:
                    print '  $ new tree'
                for k in child:
                    print '  *', k
        else:
            print '  * leaf, nothing pushed'
        print '* Finished, self._dfs_q: %d' % (len(self._dfs_q), )


class RuleInterval(object):
    def __init__(self, rule, start, end):
        self.rule = rule
        self.start = start
        self.end = end

    def __str__(self):
        return '%s [%d,%d]' % (self.rule, self.start, self.end, )

    def __eq__(self, other):
        return (self.rule == other.rule and 
                    self.start == other.start and
                    self.end == other.end)    

class Pair(object):
    def __init__(self, father, child, indexes=None):
        self.father = father
        self.child = child
        if indexes:
            self.i, self.k, self.j = indexes
        self.is_leaf = self.child.is_terminal

    def __str__(self):
        return 'F: %s [%d,%d] | C: %s [%d,%d]' % (self.father, 
            self.k, self.j, self.child, self.i, self.j, )

    def __eq__(self, other):
        return (self.father == other.father and self.child == other.child and
                    self.i == other.i and self.j == other.j and self.k == other.k)

    def get_father_rule_interval(self):
        return RuleInterval(self.father, self.k, self.j)

    def get_child_rule_interval(self):
        return RuleInterval(self.child, self.i, self.j)


class Node(object):
    print_accumulator = []

    def __init__(self, value, children):
        self.value = value
        self.children = children
        self.is_leaf = self.value.rule.is_terminal

    @classmethod
    def put(cls, chars):
        cls.print_accumulator.append(chars)

    def list_print(self):
        # print '--'
        print_accumulator = type(self).print_accumulator = []
        self.list_representation()
        print ''

        ### Insert spaces between ) and symbols
        for index, chunk in enumerate(print_accumulator[:-1]):
            if chunk[-1] == ')' and print_accumulator[index + 1][0] not in (' ', ')', ):
                print_accumulator[index + 1] = ' %s' % (print_accumulator[index + 1], )

        print ''.join(print_accumulator)

    def list_representation(self):
        put = type(self).put
        put('(')
        if self.value.rule.is_terminal:
            put(self.value.rule.production)

        else:
            prods = self.value.rule.production.split()
            if len(prods) == 1:
                put(prods[0])
                put(' ')
                self.children[0].list_representation()
                
            elif len(prods) == 2:
                put(prods[0])
                put(' ')
                self.children[0].list_representation()
                put(prods[1])
                put(' ')
                self.children[1].list_representation()

            else:
                raise ValueError('More than 2 productions for %s' % (self.value, ))

        put(')')

    def __str__(self):
        return str(self.value)

    def get(self, value):
        if self.value == value:
            return self
        for child in self.children:
            result = child.get(value)
            if result:
                return result
        return None

    def count_leafs(self):
        if self.is_leaf:
            return 1
        else:
            result = 0
            for child in self.children:
                result += child.count_leafs()
            return result